package com.hqq.exercise.divide_conquer;

import java.util.Arrays;

/**
 * BigNum 大数操作
 * Created by heqianqian on 2017/8/28.
 */
public class BigNum {

    private static final int CHAR_BASE = 96;

    /**
     * 两个大正数相加
     */
    public static void add(char[] num1, char[] num2) {
        int length = num1.length > num2.length ? num1.length : num2.length;
        char[] number1 = format(num1, length);
        char[] number2 = format(num2, length);
        int[] result = new int[length + 1];//防止最高位产生进位
        int carry = 0;//进位
        int temp;//临时结果
        for (int i = 0; i < length; i++) {
            //中间结果
            temp = carry + number1[i] + number2[i] - 96;
            //判断是否产生进位
            if (temp >= 10) {
                carry = 1;
                temp = temp % 10;
            } else {
                carry = 0;
            }
            result[i] = temp;
        }
        result[result.length - 1] = carry;
        printResult(result);
    }

    /**
     * 大整数的减法
     */
    public static void sub(char[] num1, char[] num2) {
        int length = num1.length > num2.length ? num1.length : num2.length;
        char[] number1 = format(num1, length);
        char[] number2 = format(num2, length);
        int[] result = new int[length + 1];//防止最高位产生进位
        int carry = 0;//进位
        int temp;//临时结果
        for (int i = 0; i < length; i++) {
            temp = number1[i] - number2[i] + carry;
            if (temp < 0) {
                carry = -1;
                temp = temp + 10;
            } else {
                carry = 0;
            }
            result[i] = temp;
        }
        result[result.length - 1] = carry;
        printResult(result);
    }

    private static void printResult(int[] array) {
        //逆序输出 排除先导0
        boolean isPrefixZero = true;
        for (int i = array.length - 1; i >= 0; i--) {
            if (array[i] == 0 && isPrefixZero) {
                continue;
            } else {
                isPrefixZero = false;
                System.out.print(array[i]);
            }
        }
    }

    /**
     * 格式化大整数数组
     * 数组逆序存储 并且高位补0
     */
    public static char[] format(char[] num, int length) {
        char[] result = new char[length];
        /*逆序存储*/
        for (int i = 0; i < num.length; i++) {
            result[i] = num[num.length - i - 1];
        }
        /*补充前导0*/
        for (int i = 0; i < length - num.length; i++) {
            result[num.length + i] = '0';
        }
        return result;
    }


    public static void main(String[] args) {
        String num2 = "164681654767446887797451316158";
        String num1 = "168746315641347979798";
        add(num1.toCharArray(), num2.toCharArray());
        System.out.println();
        sub("567".toCharArray(), "123".toCharArray());
    }
}
